package com.algorithm;

/**
 * 字谜问题,结题思路
 * 1.横向遍历二位数组
 * 2.纵向遍历二维数组
 * 3.斜向(左下/右下)遍历二位数组
 * 遍历时,从正反两个方向将字符拼接为字符串,然后判断字符串中是否包含单词.难点在于斜向遍历时,如何取得元素的索引
 * 原理如下:以右下遍历为例
 * 可以将这些元素看做是以charades[3][0]为原点的坐标系上的点,那么这些点分别在
 *        y = x + 3, x = 0;
 *        y = x + 2, x ∈ [0, 1];
 *        y = x + 1, x ∈ [0, 2];
 *        y = x, x ∈ [0, 3];
 *        y = x - 1, x ∈ [1, 3];
 *        y = x - 2, x ∈ [2, 3];
 *        y = x - 3, x = 3;
 * 所表示的直线上,这里x ∈ Z, y ∈ Z.
 * 上面的几个函数唯一的区别就是函数的常数项和取值范围在变,而且常数和x的取值范围有密切关系.所以用一个抽象的表达式表示为
 *   y = x + k; k ∈ Z, k ∈ [-3, 3],当k >= 0时 x ∈ [0, 3-k]; 当k < 0 时 x ∈ [-k, 3]
 * 同理左下遍历是可得,
 *   y = -x + k; k ∈ Z, k ∈ [0, 6],当k >= 3时 x ∈ [k-3, 3]; 当k < 3 时 x ∈ [0, k]
 * 这里的x和y即二维数组元素的横纵坐标也就是索引,将上面的关系转换为for循环则很快可以得出结论
 *
 * Created by houjinxin on 16/5/5.
 */
public class Charades {

    public static final String[] words = {
            "this", "two", "fat", "that"
    };

    public static final String[][] charades = {
            {"t", "h", "i", "s"},
            {"w", "a", "t", "s"},
            {"o", "a", "h", "g"},
            {"f", "g", "d", "t"},
    };

    public static void main(String[] args) {
        for (String word : words) {
            String temp = ""; //正向排列
            String reverseTemp = ""; //反向排列
            //横向检查
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    temp += charades[i][j];
                    reverseTemp = charades[i][j] + reverseTemp;
                }
                if (temp.contains(word)) {
                    System.out.println("单词" + word + "在第" + (i + 1) + "行");
                } else if (reverseTemp.contains(word)) {
                    System.out.println("单词" + word + "在第" + (i + 1) + "行");
                }
                temp = "";
                reverseTemp = "";
            }
            //纵向检查
            for (int k = 0; k < 4; k++) {
                for (int j = 0; j < 4; j++) {
                    temp += charades[j][k];
                    reverseTemp = charades[j][k] + reverseTemp;
                }
                if (temp.contains(word)) {
                    System.out.println("单词" + word + "在第" + (k + 1) + "列");
                } else if (reverseTemp.contains(word)) {
                    System.out.println("单词" + word + "在第" + (k + 1) + "列");
                }
                temp = "";
                reverseTemp = "";
            }
            //斜向检查 右下
            for (int k = -3; k <= 3; k++) {
                if (k < 0) {
                    for (int x = -k; x <= 3; x++) {
                        temp += charades[x][x + k];
                        reverseTemp = charades[x][x + k] + reverseTemp;
                    }
                } else {
                    for (int x = 0; x <= 3 - k; x++) {
                        temp += charades[x][x + k];
                        reverseTemp = charades[x][x + k] + reverseTemp;
                    }
                }
                if (temp.contains(word)) {
                    System.out.println("单词" + word + "在以charades[3][0]为原点的坐标系的y=x+" + k + "表示的直线上");
                } else if (reverseTemp.contains(word)) {
                    System.out.println("单词" + word + "在以charades[3][0]为原点的坐标系的y=x+" + k + "表示的直线上");
                }
                temp = "";
                reverseTemp = "";
            }
            //斜向检查 左下
            for (int k = 0; k <= 6; k++) {
                if (k < 3) {
                    for (int x = 0; x <= k; x++) {
                        temp += charades[x][-x + k];
                        reverseTemp = charades[x][-x + k] + reverseTemp;
                    }
                } else {
                    for (int x = k - 3; x <= 3; x++) {
                        temp += charades[x][-x + k];
                        reverseTemp = charades[x][-x + k] + reverseTemp;
                    }
                }
                if (temp.contains(word)) {
                    System.out.println("单词" + word + "在以charades[3][0]为原点的坐标系的y=-x+" + k + "表示的直线上");
                } else if (reverseTemp.contains(word)) {
                    System.out.println("单词" + word + "在以charades[3][0]为原点的坐标系的y=-x+" + k + "表示的直线上");
                }
                temp = "";
                reverseTemp = "";
            }
        }
    }
}
